package KEY;

import org.junit.jupiter.api.Test;
import tool.s;

import java.util.*;

/**
 * @Author: Siantar
 * @Date: 2023-11-14-17:25
 * @Description: 1.0
 */
public class Dijkstra {
    public List<int[]>[] creatTable(int[][] edges, int n) {
        List<int[]>[] mp = new List[n];
        for (int i = 0; i < n; ++i) {
            mp[i] = new ArrayList<int[]>();
        }
        for (int[] e : edges) {
            int from = e[0], to = e[1], weight = e[2];
            mp[from].add(new int[]{to, weight});
            mp[to].add(new int[]{from, weight});
        }
        return mp;
    }

    public int[] dijkstra(List<int[]>[] mp, int s) {
        int n = mp.length;
        int[] dis = new int[n];
        boolean[] vis = new boolean[n];
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);
        Arrays.fill(dis, Integer.MAX_VALUE / 2);
        dis[s] = 0;
        queue.offer(new int[]{s, 0});
        while (!queue.isEmpty()) {
            int u = queue.poll()[0];
            if (vis[u]) continue;
            vis[u] = true;
            for (int[] vw : mp[u]) {
                int v = vw[0], w = vw[1];
                //核心代码
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    queue.offer(new int[]{v, dis[v]});
                }
            }
        }
        return dis;
    }
    @Test
    public void test() {
        int[][] edges = new int[][]{{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
        int n = 4;
        List<int[]>[] mp = creatTable(edges, n);
        int[] dis = dijkstra(mp, 0);
        s.print(dis);
    }
}
